import java.util.stream.IntStream;

/**
 * 贪心算法-K次取反后最大化的数组和-力扣1005
 */
public class Practice_3 {
    public static void main(String[] args) {
        int[] nums = {2,-3,-1,5,-4};
        int k = 2;
        int result = largestSumAfterKNegations(nums, k);
        System.out.println(result);
    }
    public static int largestSumAfterKNegations(int[] nums, int k) {
        //按绝对值降序排列----重点
        nums = IntStream.of(nums)
                .boxed()
                .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                .mapToInt(Integer::intValue).toArray();

        int length = nums.length;
        for (int i = 0; i < nums.length; i++) {//第一次贪心，把所有能改的负数都改了
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k = k - 1;
            }
        }
        if (k % 2 == 1) {//第二次贪心，只改绝对值最小的值
            nums[length - 1] = -nums[length - 1];
        }
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum = sum + nums[i];
        }
        return sum;
    }
}
